package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test

/**
 *
 * https://leetcode.cn/problems/most-frequent-subtree-sum/description
 *
 * 题型： 二叉树 - 后序遍历 + 哈希法(hash map)
 *
 * ```
 * # 508. 出现次数最多的子树元素和
 * https://leetcode.cn/problems/most-frequent-subtree-sum/description
 * 给你一个二叉树的根结点 root ，请返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。
 * 一个结点的 「子树元素和」 定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。
 *
 *
 * 示例 1：
 * https://assets.leetcode.com/uploads/2021/04/24/freq1-tree.jpg
 * 输入: root = [5,2,-3]
 * 输出: [2,-3,4]
 *
 * 示例 2：
 * https://assets.leetcode.com/uploads/2021/04/24/freq2-tree.jpg
 *
 * 输入: root = [5,2,-5]
 * 输出: [2]
 *
 * 提示:
 * 节点数在 [1, 104] 范围内
 * -105 <= Node.val <= 105
 * ```
 */

class leetcode_508 {
    @Test
    fun test_1() {
        // 5,2,-3
        val n5 = TreeNode(5)
        val n2 = TreeNode(2)
        val n3 = TreeNode(-3)
        val root = n5
        n5.left = n2
        n5.right = n3
        val actual = findFrequentTreeSum(root)
        val expected: IntArray = intArrayOf(2, -3, 4)
        Assert.assertEquals(expected.contentToString(), actual.contentToString())
    }

    @Test
    fun test_2() {
        // 5,2,-3
        val n5 = TreeNode(5)
        val n2 = TreeNode(2)
        val n5_2 = TreeNode(-5)
        val root = n5
        n5.left = n2
        n5.right = n5_2
        val actual = findFrequentTreeSum(root)
        val expected: IntArray = intArrayOf(2)
        Assert.assertEquals(expected.contentToString(), actual.contentToString())
    }


    /**
    1 理解题：
    举一个大一点的树就明白了，如这样一颗树：

    5
    / \
    2   -3
    /    \
    4     -1
    子树和会计算为：

    5的子树和： 5 + 2 + 4 + (-1) + (-3) = 7
    2的子树和： 2 + 4 + (-1) = 5
    -3的子树和：-3
    4的子树和： 4
    -1的子树和：-1
    输出将是所有子树和，因为它们都出现一次，返回 [7, 5, -3, 4, -1]。

    2 题型： 二叉树 - 后序遍历 + 哈希法(hash map)


    2 思路:
    （1）题目要求使用自下而上，这样下面的和，再上一层直接使用，且没有重复操作。因此，使用后序遍历。
    （2）使用HashMap (key = sum，value= sum的 次数)来统计出现sum 次数，然后找出次数最多的sum

    https://leetcode.cn/problems/most-frequent-subtree-sum/solutions/3041498/du-dong-ti-xiang-jie-ji-jian-dai-ma-by-f-uzyp
     */
    private fun findFrequentTreeSum(root: TreeNode?): IntArray {
        val map: HashMap<Int, Int> = HashMap()
        collect(root, map)

        // 找出value 的最大值
        val max = map.values.max()
        // 根据 max 过滤 map,然后得出 keys

        val result = map.filter {
            it.value == max
        }.map {
            it.key
        }.toIntArray()
        return result
    }

    fun collect(root: TreeNode?, map: HashMap<Int, Int>): Int {
        // 1 确定函数参数以及返回值
        // 2 确认终止条件
        if (null == root) {
            return 0
        }
        // 3 确定单次递归的终止条件： 后序遍历
        // 左
        val left = collect(root.left, map)

        // 右
        val right = collect(root.right, map)

        // 中
        val sum = left + right + root.`val`
        println("sum=$sum")
        map[sum] = (map[sum] ?: 0) + 1
        return sum
    }

    private fun findFrequentTreeSum2(root: TreeNode?): IntArray {
        val map: HashMap<Int, Int> = HashMap()
        dp(root, map)

        return getMaxCount(map)
    }

    fun getMaxCount(map: HashMap<Int, Int>): IntArray {
        if (map.isEmpty()) {
            return intArrayOf()
        }

        // 找出value 的最大值
        val maxValue = map.values.max()

        val result = map.entries
            .filter {
                // 过滤map，只包含最大值
                it.value == maxValue
            }
            .map {
                // 转换成 key ArrayList
                it.key
            }
            // 转换成 key IntAray
            .toIntArray()
        return result
    }

    private fun dp(root: TreeNode?, map: HashMap<Int, Int>): Int {
        // 1 确定函数参数，以及返回值
        // 2 确定终止条件
        // 3 收集结果
        if (root == null) {
            return 0
        }

        // 3 确定单层递归的逻辑：后序遍历（左右中）

        // 左
        val sumLeft: Int = dp(root.left, map)

        // 右
        val sumRight: Int = dp(root.right, map)

        // 中
        val sum: Int = if (root.left == null && root.right == null) {
            root.`val`
        } else {
            root.`val` + sumLeft + sumRight
        }
        if (map.contains(sum)) {
            val count = map[sum] ?: 0
            map.put(sum, count + 1)
        } else {
            map.put(sum, 1)
        }
        return sum
    }
}